package com.ywgt;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int [] arr={1256,265,2466,32,0,124,12,2656,246,49};
        //stepSort(arr);
        insertSort(arr);
    }

    /**
     * 希尔排序交换法
     * @param arr
     */
    public static void stepSort(int [] arr){
        int temp=0;
        for (int step = arr.length/2; step >0; step/=2) { //每次循环的步长 也就是分组数量 10个元素 第一次份五组
            // 步长为5 意思为下标0和下标为5的元素为一组，比较并交换
            for (int j = step; j < arr.length; j++) { //循环多少个组的次数
                for (int k = j-step; k >=0; k-=step) {//每个分组按照一定的步长进行遍历比较交换
                    if(arr[k]>arr[k+step]){
                        temp=arr[k];
                        arr[k]=arr[k+step];
                        arr[k+step]=temp;
                        System.out.println(Arrays.toString(arr));
                    }

                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * shell排序位移法
     * @param arr
     */
    public static void insertSort(int [] arr){

        for (int step = arr.length/2; step >0; step/=2){
            for (int i = step; i <arr.length ; i++) {
                //将每个分组看做一个插入排序，将第一个元素的下标作为待插入下标，全部将第一个元素的下标看做0进行处理
                int insertIndex=i-step;
                int insertVal=arr[i];
                while(insertIndex>=0&&insertVal<arr[insertIndex]){
                    arr[insertIndex+step]=arr[insertIndex];
                    insertIndex-=step;
                }
                    arr[insertIndex+step]=insertVal;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}
